<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.9.0">
    

    

    



    <meta charset="utf-8">
    
    
    
    
    <title>详解Stack的实现方式及其应用 | 欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~ | It&#39;s founded on March 9, 2019 and the open source address for the blog notes https://github.com/YUbuntu0109/YUbuntu0109.github.io</title>
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    
    <meta name="theme-color" content="#3F51B5">
    
    
    <meta name="keywords" content="Java,Data Structures and Algorithms">
    <meta name="description" content="栈栈的定义 : 栈(Stack)是一个有序线性表,只能在表的一端(称为栈顶 : top)执行插入和删除操作.最后插入的元素将第一个被删除.所以,栈也称为后进先出(Last In Frist Out: LIFO)或先进后出(Fist In Last Out: FILO)线性表.注意点 : 两个改变栈的操作都有专用名称,一个称为入栈(psuh): 表示在栈中插入一个元素. 另一个称为出栈(pop):">
<meta name="keywords" content="Java,Data Structures and Algorithms">
<meta property="og:type" content="article">
<meta property="og:title" content="详解Stack的实现方式及其应用">
<meta property="og:url" content="http://yoursite.com/2019/04/13/详解Stack的实现方式及其应用/index.html">
<meta property="og:site_name" content="欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~">
<meta property="og:description" content="栈栈的定义 : 栈(Stack)是一个有序线性表,只能在表的一端(称为栈顶 : top)执行插入和删除操作.最后插入的元素将第一个被删除.所以,栈也称为后进先出(Last In Frist Out: LIFO)或先进后出(Fist In Last Out: FILO)线性表.注意点 : 两个改变栈的操作都有专用名称,一个称为入栈(psuh): 表示在栈中插入一个元素. 另一个称为出栈(pop):">
<meta property="og:locale" content="en">
<meta property="og:image" content="http://yoursite.com/2019/04/13/详解Stack的实现方式及其应用/ListStack.PNG">
<meta property="og:updated_time" content="2019-10-31T05:19:50.761Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="详解Stack的实现方式及其应用">
<meta name="twitter:description" content="栈栈的定义 : 栈(Stack)是一个有序线性表,只能在表的一端(称为栈顶 : top)执行插入和删除操作.最后插入的元素将第一个被删除.所以,栈也称为后进先出(Last In Frist Out: LIFO)或先进后出(Fist In Last Out: FILO)线性表.注意点 : 两个改变栈的操作都有专用名称,一个称为入栈(psuh): 表示在栈中插入一个元素. 另一个称为出栈(pop):">
<meta name="twitter:image" content="http://yoursite.com/2019/04/13/详解Stack的实现方式及其应用/ListStack.PNG">
    
        <link rel="alternate" type="application/atom+xml" title="欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~" href="/atom.xml">
    
    <link rel="shortcut icon" href="/favicon.ico">
    <link rel="stylesheet" href="//unpkg.com/hexo-theme-material-indigo@latest/css/style.css">
    <script>window.lazyScripts=[]</script>

    <!-- custom head -->
    

</head>

<body>
    <div id="loading" class="active"></div>

    <aside id="menu" class="hide" >
  <div class="inner flex-row-vertical">
    <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="menu-off">
        <i class="icon icon-lg icon-close"></i>
    </a>
    <div class="brand-wrap" style="background-image:url(/img/brand.jpg)">
      <div class="brand">
        <a href="/" class="avatar waves-effect waves-circle waves-light">
          <img src="/img/my-portrait.jpg">
        </a>
        <hgroup class="introduce">
          <h5 class="nickname">黄宇辉</h5>
          <a href="mailto:3083968068@qq.com" title="3083968068@qq.com" class="mail">3083968068@qq.com</a>
        </hgroup>
      </div>
    </div>
    <div class="scroll-wrap flex-col">
      <ul class="nav">
        
            <li class="waves-block waves-effect">
              <a href="/"  >
                <i class="icon icon-lg icon-home"></i>
                homepage
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/archives"  >
                <i class="icon icon-lg icon-archives"></i>
                Archives
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/tags"  >
                <i class="icon icon-lg icon-tags"></i>
                Tags
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/categories"  >
                <i class="icon icon-lg icon-th-list"></i>
                Categories
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://github.com/YUbuntu0109" target="_blank" >
                <i class="icon icon-lg icon-github"></i>
                Github
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://github.com/YUbuntu0109" target="_blank" >
                <i class="icon icon-lg icon-weibo"></i>
                Weibo
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/custom"  >
                <i class="icon icon-lg icon-link"></i>
                Test
              </a>
            </li>
        
      </ul>
    </div>
  </div>
</aside>

    <main id="main">
        <header class="top-header" id="header">
    <div class="flex-row">
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light on" id="menu-toggle">
          <i class="icon icon-lg icon-navicon"></i>
        </a>
        <div class="flex-col header-title ellipsis">详解Stack的实现方式及其应用</div>
        
        <div class="search-wrap" id="search-wrap">
            <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="back">
                <i class="icon icon-lg icon-chevron-left"></i>
            </a>
            <input type="text" id="key" class="search-input" autocomplete="off" placeholder="Search">
            <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="search">
                <i class="icon icon-lg icon-search"></i>
            </a>
        </div>
        
        
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="menuShare">
            <i class="icon icon-lg icon-share-alt"></i>
        </a>
        

        <!-- background music(Mar 11,2019 AM) -->
        <div>
            <iframe frameborder="no" border="0" marginwidth="0" marginheight="0" width=280 height=52 src="//music.163.com/outchain/player?type=2&id=438801642&auto=1&height=32"></iframe>
        </div>
        <!---------------------->
    </div>
</header>
<header class="content-header post-header">

    <div class="container fade-scale">
        <h1 class="title">详解Stack的实现方式及其应用</h1>
        <h5 class="subtitle">
            
                <time datetime="2019-04-13T10:00:01.000Z" itemprop="datePublished" class="page-time">
  2019-04-13
</time>


            
        </h5>
    </div>

    


</header>


<div class="container body-wrap">
    
    <aside class="post-widget">
        <nav class="post-toc-wrap post-toc-shrink" id="post-toc">
            <h4>TOC</h4>
            <ol class="post-toc"><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#栈"><span class="post-toc-number">1.</span> <span class="post-toc-text">栈</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#栈的定义-栈-Stack-是一个有序线性表-只能在表的一端-称为栈顶-top-执行插入和删除操作-最后插入的元素将第一个被删除-所以-栈也称为后进先出-Last-In-Frist-Out-LIFO-或先进后出-Fist-In-Last-Out-FILO-线性表"><span class="post-toc-number">1.1.</span> <span class="post-toc-text">栈的定义 : 栈(Stack)是一个有序线性表,只能在表的一端(称为栈顶 : top)执行插入和删除操作.最后插入的元素将第一个被删除.所以,栈也称为后进先出(Last In Frist Out: LIFO)或先进后出(Fist In Last Out: FILO)线性表.</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#注意点-两个改变栈的操作都有专用名称-一个称为入栈-psuh-表示在栈中插入一个元素-另一个称为出栈-pop-表示从栈中删除一个元素-试图对一个空栈执行出栈的操作称为下溢-underflow-试图对一个满栈执行入栈操作称为溢出-overflow-通常溢出和下溢均被认为是异常"><span class="post-toc-number">1.2.</span> <span class="post-toc-text">注意点 : 两个改变栈的操作都有专用名称,一个称为入栈(psuh): 表示在栈中插入一个元素. 另一个称为出栈(pop): 表示从栈中删除一个元素.试图对一个空栈执行出栈的操作称为下溢(underflow). 试图对一个满栈执行入栈操作称为溢出(overflow). 通常溢出和下溢均被认为是异常.</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#栈的应用"><span class="post-toc-number">1.3.</span> <span class="post-toc-text">栈的应用</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#推荐学习方法"><span class="post-toc-number">1.4.</span> <span class="post-toc-text">推荐学习方法</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#栈的实现方式"><span class="post-toc-number">1.5.</span> <span class="post-toc-text">栈的实现方式</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#局限性-栈的最大空间必须预先声明且不能改变-试图对一个满栈执行入栈时操作将产生一个针对简单数组这种特定实现栈方式的异常"><span class="post-toc-number">1.5.1.</span> <span class="post-toc-text">局限性 : 栈的最大空间必须预先声明且不能改变.试图对一个满栈执行入栈时操作将产生一个针对简单数组这种特定实现栈方式的异常 !</span></a></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#注意-倍增太多可能导致内存溢出"><span class="post-toc-number">1.5.2.</span> <span class="post-toc-text">注意 : 倍增太多可能导致内存溢出 !</span></a></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#上述程序中利用重复倍增技术-提高了程序的性能-其总时间开销T-n-≈-O-n-相比采用-当栈满时-每次将数组的大小增加1更加节省了push操作的总时间开销-其总时间开销T-n-≈-O-n²"><span class="post-toc-number">1.5.3.</span> <span class="post-toc-text">上述程序中利用重复倍增技术)提高了程序的性能,其总时间开销T(n) ≈ O(n) . 相比采用: 当栈满时,每次将数组的大小增加1更加节省了push操作的总时间开销.其总时间开销T(n) ≈ O(n²) .</span></a></li></ol></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#栈的各种实现方法的比较"><span class="post-toc-number">1.6.</span> <span class="post-toc-text">栈的各种实现方法的比较</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#a-：基于数组实现的栈"><span class="post-toc-number">1.6.1.</span> <span class="post-toc-text">(a) ：基于数组实现的栈</span></a></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#b-：基于链表实现的栈"><span class="post-toc-number">1.6.2.</span> <span class="post-toc-text">(b) ：基于链表实现的栈</span></a></li></ol></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#栈的应用-1"><span class="post-toc-number">1.7.</span> <span class="post-toc-text">栈的应用</span></a></li></ol></li></ol>
        </nav>
    </aside>


<article id="post-详解Stack的实现方式及其应用"
  class="post-article article-type-post fade" itemprop="blogPost">

    <div class="post-card">
        <h1 class="post-card-title">详解Stack的实现方式及其应用</h1>
        <div class="post-meta">
            <time class="post-time" title="2019-04-13 10:00:01" datetime="2019-04-13T10:00:01.000Z"  itemprop="datePublished">2019-04-13</time>

            


            

        </div>
        <div class="post-content" id="post-content" itemprop="postContent">
            <h2 id="栈"><a href="#栈" class="headerlink" title="栈"></a>栈</h2><h3 id="栈的定义-栈-Stack-是一个有序线性表-只能在表的一端-称为栈顶-top-执行插入和删除操作-最后插入的元素将第一个被删除-所以-栈也称为后进先出-Last-In-Frist-Out-LIFO-或先进后出-Fist-In-Last-Out-FILO-线性表"><a href="#栈的定义-栈-Stack-是一个有序线性表-只能在表的一端-称为栈顶-top-执行插入和删除操作-最后插入的元素将第一个被删除-所以-栈也称为后进先出-Last-In-Frist-Out-LIFO-或先进后出-Fist-In-Last-Out-FILO-线性表" class="headerlink" title="栈的定义 : 栈(Stack)是一个有序线性表,只能在表的一端(称为栈顶 : top)执行插入和删除操作.最后插入的元素将第一个被删除.所以,栈也称为后进先出(Last In Frist Out: LIFO)或先进后出(Fist In Last Out: FILO)线性表."></a>栈的定义 : <code>栈(Stack)</code>是一个有序线性表,只能在表的一端(称为栈顶 : top)执行插入和删除操作.最后插入的元素将第一个被删除.所以,栈也称为后进先出(Last In Frist Out: <code>LIFO</code>)或先进后出(Fist In Last Out: <code>FILO</code>)线性表.</h3><h3 id="注意点-两个改变栈的操作都有专用名称-一个称为入栈-psuh-表示在栈中插入一个元素-另一个称为出栈-pop-表示从栈中删除一个元素-试图对一个空栈执行出栈的操作称为下溢-underflow-试图对一个满栈执行入栈操作称为溢出-overflow-通常溢出和下溢均被认为是异常"><a href="#注意点-两个改变栈的操作都有专用名称-一个称为入栈-psuh-表示在栈中插入一个元素-另一个称为出栈-pop-表示从栈中删除一个元素-试图对一个空栈执行出栈的操作称为下溢-underflow-试图对一个满栈执行入栈操作称为溢出-overflow-通常溢出和下溢均被认为是异常" class="headerlink" title="注意点 : 两个改变栈的操作都有专用名称,一个称为入栈(psuh): 表示在栈中插入一个元素. 另一个称为出栈(pop): 表示从栈中删除一个元素.试图对一个空栈执行出栈的操作称为下溢(underflow). 试图对一个满栈执行入栈操作称为溢出(overflow). 通常溢出和下溢均被认为是异常."></a>注意点 : 两个改变栈的操作都有专用名称,一个称为<code>入栈(psuh)</code>: 表示在栈中插入一个元素. 另一个称为<code>出栈(pop)</code>: 表示从栈中删除一个元素.试图对一个空栈执行出栈的操作称为<code>下溢(underflow)</code>. 试图对一个满栈执行入栈操作称为<code>溢出(overflow)</code>. 通常溢出和下溢均被认为是异常.</h3><h3 id="栈的应用"><a href="#栈的应用" class="headerlink" title="栈的应用"></a>栈的应用</h3><ul>
<li><em>直接应用</em></li>
</ul>
<ol>
<li>符号匹配.</li>
<li>中缀表达式转换为后缀表达式.</li>
<li>计算后缀表达式.</li>
<li>实现函数的调用(包括递归).</li>
<li>求范围误差(极差).</li>
<li>网页浏览器中已访问页面的历史记录(后退back按钮).</li>
<li>文本编辑器中的撤销(undo)序列.</li>
<li>HTML和XML文件中的标签(tag)匹配.</li>
</ol>
<ul>
<li><em>间接应用</em></li>
</ul>
<ol>
<li>作为一个算法的辅助数据结构(例如: 树的遍历算法).</li>
<li>其它数据结构的组件(例如: 模拟队列).</li>
</ol>
<h3 id="推荐学习方法"><a href="#推荐学习方法" class="headerlink" title="推荐学习方法"></a>推荐学习方法</h3><ul>
<li><em>推荐小伙伴们一个数据结构可视化的网站,可以大大提高学习效率哟(っ•̀ω•́)っ✎⁾⁾⁾ <a href="https://www.cs.usfca.edu/~galles/visualization/about.html" target="_blank" rel="noopener">GO !</a></em><figure class="image-bubble">
                <div class="img-lightbox">
                    <div class="overlay"></div>
                    <img src="/2019/04/13/详解Stack的实现方式及其应用/ListStack.PNG" alt title>
                </div>
                <div class="image-caption"></div>
            </figure>
</li>
</ul>
<h3 id="栈的实现方式"><a href="#栈的实现方式" class="headerlink" title="栈的实现方式"></a>栈的实现方式</h3><ol>
<li>基于简单数组的实现栈 ：程序示例如下*<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@ClassName</span>: SimpleStack</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span>: 利用简单数组实现栈</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span>: HuangYuhui</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> &lt;T&gt;</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@date</span>: Apr 10, 2019 4:15:47 PM</span></span><br><span class="line"><span class="comment"> * </span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">SimArrayStack</span>&lt;<span class="title">T</span>&gt; </span>&#123;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// the size of stack</span></span><br><span class="line">	<span class="keyword">private</span> <span class="keyword">int</span> maxSize;</span><br><span class="line">	<span class="comment">// store the data</span></span><br><span class="line">	<span class="keyword">private</span> Object[] stackArray;</span><br><span class="line">	<span class="comment">// the top pointer of the stack</span></span><br><span class="line">	<span class="keyword">private</span> <span class="keyword">int</span> topPointer;</span><br><span class="line"></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="title">SimArrayStack</span><span class="params">(<span class="keyword">int</span> max)</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">		maxSize = max;</span><br><span class="line">		topPointer = -<span class="number">1</span>;</span><br><span class="line">		stackArray = <span class="keyword">new</span> Object[maxSize];</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// push new data into the stack</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> T <span class="title">push</span><span class="params">(T element)</span> </span>&#123;</span><br><span class="line">		stackArray[++topPointer] = element;</span><br><span class="line">		<span class="keyword">return</span> element;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// peek the top data in the stack</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> Object <span class="title">peek</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">return</span> stackArray[topPointer];</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// determines whether the stack is empty</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">return</span> topPointer == -<span class="number">1</span>;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// pop the data in the stack</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> Object <span class="title">pop</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">return</span> stackArray[topPointer--];</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// pop all of data in the stack</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">popAll</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">if</span> (isEmpty()) &#123;</span><br><span class="line">			<span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">while</span> (!isEmpty()) &#123;</span><br><span class="line">			System.out.println(<span class="string">"The element to be poped : "</span> + pop());</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// Iterate through all the data in the stack</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">traverseElement</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		System.out.print(<span class="string">"All of element in the stack : "</span>);</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; stackArray.length; i++) &#123;</span><br><span class="line">			<span class="keyword">if</span> (i != stackArray.length - <span class="number">1</span>) &#123;</span><br><span class="line">				System.out.print(stackArray[i] + <span class="string">" , "</span>);</span><br><span class="line">			&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">				System.out.print(stackArray[i]);</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		System.out.println();</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// Test</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">		<span class="comment">// SimpleStack&lt;Character&gt; stack2 = new SimpleStack&lt;Character&gt;(6);</span></span><br><span class="line">		SimArrayStack&lt;Integer&gt; stack = <span class="keyword">new</span> SimArrayStack&lt;Integer&gt;(<span class="number">6</span>);</span><br><span class="line">		stack.push(<span class="number">1</span>);</span><br><span class="line">		stack.push(<span class="number">2</span>);</span><br><span class="line">		stack.push(<span class="number">3</span>);</span><br><span class="line">		stack.push(<span class="number">4</span>);</span><br><span class="line">		stack.push(<span class="number">5</span>);</span><br><span class="line">		stack.push(<span class="number">6</span>);</span><br><span class="line"></span><br><span class="line">		stack.traverseElement();</span><br><span class="line">		System.out.println(<span class="string">"The element to be poped : "</span> + stack.pop());</span><br><span class="line">		System.out.println(<span class="string">"The top element : "</span> + stack.peek());</span><br><span class="line">		System.out.println(<span class="string">"Push a new element : "</span> + stack.push(<span class="number">7</span>));</span><br><span class="line">		System.out.println(<span class="string">"The top element : "</span> + stack.peek());</span><br><span class="line">		System.out.println(<span class="string">"Determines whether the stack is empty : "</span> + stack.isEmpty());</span><br><span class="line">		System.out.println(<span class="string">"Pop all of elements : "</span> + stack.popAll());</span><br><span class="line">		System.out.println(<span class="string">"Determines whether the stack is empty : "</span> + stack.isEmpty());</span><br><span class="line"></span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/* ## The program running results are as follows :</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">All of element in the stack : 1 , 2 , 3 , 4 , 5 , 6</span></span><br><span class="line"><span class="comment">The element to be poped : 6</span></span><br><span class="line"><span class="comment">The top element : 5</span></span><br><span class="line"><span class="comment">Push a new element : 7</span></span><br><span class="line"><span class="comment">The top element : 7</span></span><br><span class="line"><span class="comment">Determines whether the stack is empty : false</span></span><br><span class="line"><span class="comment">The element to be poped : 7</span></span><br><span class="line"><span class="comment">The element to be poped : 5</span></span><br><span class="line"><span class="comment">The element to be poped : 4</span></span><br><span class="line"><span class="comment">The element to be poped : 3</span></span><br><span class="line"><span class="comment">The element to be poped : 2</span></span><br><span class="line"><span class="comment">The element to be poped : 1</span></span><br><span class="line"><span class="comment">Pop all of elements : true</span></span><br><span class="line"><span class="comment">Determines whether the stack is empty : true</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment"> */</span></span><br></pre></td></tr></table></figure>
</li>
</ol>
<h4 id="局限性-栈的最大空间必须预先声明且不能改变-试图对一个满栈执行入栈时操作将产生一个针对简单数组这种特定实现栈方式的异常"><a href="#局限性-栈的最大空间必须预先声明且不能改变-试图对一个满栈执行入栈时操作将产生一个针对简单数组这种特定实现栈方式的异常" class="headerlink" title="局限性 : 栈的最大空间必须预先声明且不能改变.试图对一个满栈执行入栈时操作将产生一个针对简单数组这种特定实现栈方式的异常 !"></a>局限性 : 栈的最大空间必须预先声明且不能改变.试图对一个满栈执行入栈时操作将产生一个针对简单数组这种特定实现栈方式的异常 !</h4><ol start="2">
<li><em>基于动态数组的实现栈 ：程序示例如下</em><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@ClassName</span>: DynArrayStack</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span>: 利用动态数组实现栈</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span>: HuangYuhui</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@date</span>: Apr 11, 2019 5:49:02 PM</span></span><br><span class="line"><span class="comment"> * </span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">DynArrayStack</span>&lt;<span class="title">T</span>&gt; </span>&#123;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">private</span> <span class="keyword">int</span> topPointer;</span><br><span class="line">	<span class="keyword">private</span> <span class="keyword">int</span> capacity;</span><br><span class="line">	<span class="keyword">private</span> Object[] array;</span><br><span class="line"></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="title">DynArrayStack</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		topPointer = -<span class="number">1</span>;</span><br><span class="line">		capacity = <span class="number">1</span>;</span><br><span class="line">		array = <span class="keyword">new</span> Object[capacity];</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// determines whether the stack is empty</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">return</span> (topPointer == -<span class="number">1</span>);</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// determines whether the stack is full</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isStackFull</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">return</span> (topPointer == capacity - <span class="number">1</span>);<span class="comment">// or return (topPointer==array.length);</span></span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// peek the top data of the stack</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> Object <span class="title">peek</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">return</span> array[topPointer];</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// push a new data into the stack</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> T <span class="title">push</span><span class="params">(T element)</span> </span>&#123;</span><br><span class="line">		<span class="keyword">if</span> (isStackFull()) &#123;</span><br><span class="line">			doubleStack();</span><br><span class="line">		&#125;</span><br><span class="line">		array[++topPointer] = element;</span><br><span class="line"></span><br><span class="line">		<span class="keyword">return</span> element;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// double the size of the array</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">doubleStack</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		Object newArr[] = <span class="keyword">new</span> Object[capacity * <span class="number">2</span>];</span><br><span class="line">		System.arraycopy(array, <span class="number">0</span>, newArr, <span class="number">0</span>, capacity);</span><br><span class="line">		capacity *= <span class="number">2</span>;</span><br><span class="line">		array = newArr;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// pop the data from the stack</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> Object <span class="title">pop</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">if</span> (isEmpty()) &#123;</span><br><span class="line">			System.err.println(<span class="string">"The Stack is  overflow !"</span>);</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> array[topPointer--];</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// pop all of data from the stack</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">popAll</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">if</span> (isEmpty()) &#123;</span><br><span class="line">			<span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">while</span> (!isEmpty()) &#123;</span><br><span class="line">			System.out.println(<span class="string">"The element to be poped : "</span> + pop());</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// Iterate through all the data in the stack</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">traverseElement</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		System.out.print(<span class="string">"all of element in the stack : "</span>);</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; array.length; i++) &#123;</span><br><span class="line">			<span class="keyword">if</span> (i != array.length - <span class="number">1</span>) &#123;</span><br><span class="line">				System.out.print(array[i] + <span class="string">" , "</span>);</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		System.out.println();</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// delete the stack</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">deleteStack</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		topPointer = -<span class="number">1</span>;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// Test</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">		DynArrayStack&lt;Character&gt; stack = <span class="keyword">new</span> DynArrayStack&lt;Character&gt;();</span><br><span class="line">		stack.push(<span class="string">'a'</span>);</span><br><span class="line">		stack.push(<span class="string">'b'</span>);</span><br><span class="line">		stack.push(<span class="string">'c'</span>);</span><br><span class="line">		stack.push(<span class="string">'d'</span>);</span><br><span class="line">		stack.push(<span class="string">'e'</span>);</span><br><span class="line">		stack.push(<span class="string">'f'</span>);</span><br><span class="line">		stack.push(<span class="string">'g'</span>);</span><br><span class="line"></span><br><span class="line">		stack.traverseElement();</span><br><span class="line">		System.out.println(<span class="string">"The element to be poped : "</span> + stack.pop());</span><br><span class="line">		System.out.println(<span class="string">"The top element : "</span> + stack.peek());</span><br><span class="line">		System.out.println(<span class="string">"Push a new element : "</span> + stack.push(<span class="string">'h'</span>));</span><br><span class="line">		System.out.println(<span class="string">"The top element : "</span> + stack.peek());</span><br><span class="line">		System.out.println(<span class="string">"Determines whether the stack is empty : "</span> + stack.isEmpty());</span><br><span class="line">		System.out.println(<span class="string">"Pop all of elements : "</span> + stack.popAll());</span><br><span class="line">		System.out.println(<span class="string">"Determines whether the stack is empty : "</span> + stack.isEmpty());</span><br><span class="line"></span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/*## The program running results are as follows :</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">all of element in the stack : a , b , c , d , e , f , g , </span></span><br><span class="line"><span class="comment">The element to be poped : g</span></span><br><span class="line"><span class="comment">The top element : f</span></span><br><span class="line"><span class="comment">Push a new element : h</span></span><br><span class="line"><span class="comment">The top element : h</span></span><br><span class="line"><span class="comment">Determines whether the stack is empty : false</span></span><br><span class="line"><span class="comment">The element to be poped : h</span></span><br><span class="line"><span class="comment">The element to be poped : f</span></span><br><span class="line"><span class="comment">The element to be poped : e</span></span><br><span class="line"><span class="comment">The element to be poped : d</span></span><br><span class="line"><span class="comment">The element to be poped : c</span></span><br><span class="line"><span class="comment">The element to be poped : b</span></span><br><span class="line"><span class="comment">The element to be poped : a</span></span><br><span class="line"><span class="comment">Pop all of elements : true</span></span><br><span class="line"><span class="comment">Determines whether the stack is empty : true</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment"> */</span></span><br></pre></td></tr></table></figure>
</li>
</ol>
<h4 id="注意-倍增太多可能导致内存溢出"><a href="#注意-倍增太多可能导致内存溢出" class="headerlink" title="注意 : 倍增太多可能导致内存溢出 !"></a>注意 : 倍增太多可能导致<code>内存溢出</code> !</h4><h4 id="上述程序中利用重复倍增技术-提高了程序的性能-其总时间开销T-n-≈-O-n-相比采用-当栈满时-每次将数组的大小增加1更加节省了push操作的总时间开销-其总时间开销T-n-≈-O-n²"><a href="#上述程序中利用重复倍增技术-提高了程序的性能-其总时间开销T-n-≈-O-n-相比采用-当栈满时-每次将数组的大小增加1更加节省了push操作的总时间开销-其总时间开销T-n-≈-O-n²" class="headerlink" title="上述程序中利用重复倍增技术)提高了程序的性能,其总时间开销T(n) ≈ O(n) . 相比采用: 当栈满时,每次将数组的大小增加1更加节省了push操作的总时间开销.其总时间开销T(n) ≈ O(n²) ."></a>上述程序中利用<code>重复倍增技术)</code>提高了程序的性能,其总时间开销<code>T(n) ≈ O(n)</code> . 相比采用: 当栈满时,每次将数组的大小增加<code>1</code>更加节省了<code>push</code>操作的总时间开销.其总时间开销<code>T(n) ≈ O(n²)</code> .</h4><ol start="3">
<li><em>基于链表来实现栈 ：程序示例如下</em><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@ClassName</span>: ListNode</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span>: 定义链表</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span>: HuangYuhui</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@date</span>: Apr 11, 2019 7:01:35 PM</span></span><br><span class="line"><span class="comment"> * </span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">ListNode</span>&lt;<span class="title">T</span>&gt; </span>&#123;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">private</span> T data;</span><br><span class="line">	<span class="keyword">private</span> ListNode&lt;T&gt; next;</span><br><span class="line"></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="title">ListNode</span><span class="params">(T d)</span> </span>&#123;</span><br><span class="line">		<span class="keyword">this</span>.data = d;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="function"><span class="keyword">public</span> T <span class="title">getData</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">return</span> data;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">setData</span><span class="params">(T data)</span> </span>&#123;</span><br><span class="line">		<span class="keyword">this</span>.data = data;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="function"><span class="keyword">public</span> ListNode&lt;T&gt; <span class="title">getNext</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">return</span> next;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">setNext</span><span class="params">(ListNode&lt;T&gt; next)</span> </span>&#123;</span><br><span class="line">		<span class="keyword">this</span>.next = next;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="meta">@Override</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> String <span class="title">toString</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="string">"["</span> + data + <span class="string">"]"</span>;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
</ol>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@ClassName</span>: ListStack</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span>: 利用链表实现栈</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span>: HuangYuhui</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@date</span>: Apr 11, 2019 6:59:46 PM</span></span><br><span class="line"><span class="comment"> * </span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">ListStack</span>&lt;<span class="title">E</span>&gt; </span>&#123;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">private</span> ListNode&lt;E&gt; headNode;</span><br><span class="line"></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="title">ListStack</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">this</span>.headNode = <span class="keyword">new</span> ListNode&lt;E&gt;(<span class="keyword">null</span>);</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// push a new node into the linked list</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> ListNode&lt;E&gt; <span class="title">push</span><span class="params">(E data)</span> </span>&#123;</span><br><span class="line">		<span class="keyword">if</span> (headNode == <span class="keyword">null</span>) &#123;</span><br><span class="line">			headNode = <span class="keyword">new</span> ListNode&lt;E&gt;(data);</span><br><span class="line">		&#125; <span class="keyword">else</span> <span class="keyword">if</span> (headNode.getData() == <span class="keyword">null</span>) &#123;</span><br><span class="line">			headNode.setData(data);<span class="comment">// initialize header node.</span></span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			ListNode&lt;E&gt; newNode = <span class="keyword">new</span> ListNode&lt;E&gt;(data); <span class="comment">// create a new node.</span></span><br><span class="line">			newNode.setNext(headNode);<span class="comment">// connect to the header node.</span></span><br><span class="line">			headNode = newNode;<span class="comment">// set the new node to header node.</span></span><br><span class="line"></span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> headNode;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// returns the top node of the linked list</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> E <span class="title">top</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">if</span> (headNode == <span class="keyword">null</span>) &#123;</span><br><span class="line">			<span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			<span class="keyword">return</span> headNode.getData();</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// pop top node in the linked list</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> E <span class="title">pop</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">if</span> (headNode == <span class="keyword">null</span>) &#123;</span><br><span class="line">			<span class="keyword">throw</span> <span class="keyword">new</span> EmptyStackException();</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			E node = headNode.getData();</span><br><span class="line">			headNode = headNode.getNext();<span class="comment">// Reset the header node.</span></span><br><span class="line">			<span class="keyword">return</span> node;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// pop all of nodes in the linked list</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">popAll</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">if</span> (headNode == <span class="keyword">null</span>) &#123;</span><br><span class="line">			<span class="keyword">throw</span> <span class="keyword">new</span> EmptyStackException();</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">while</span> (!isEmpty()) &#123;</span><br><span class="line">			System.out.println(<span class="string">"Pop all of nodes : "</span> + pop());</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span> (isEmpty()) &#123;</span><br><span class="line">			<span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// determine whether the linked list is empty</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">if</span> (headNode == <span class="keyword">null</span>) &#123;</span><br><span class="line">			<span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			<span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// Iterate through all the node in the linked list</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">getNodeByLoop</span><span class="params">(ListNode&lt;E&gt; head)</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">		<span class="keyword">if</span> (isEmpty()) &#123;</span><br><span class="line">			<span class="keyword">throw</span> <span class="keyword">new</span> EmptyStackException();</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		System.out.print(<span class="string">"All of nodes of the linked list:  "</span>);</span><br><span class="line">		<span class="keyword">while</span> (head != <span class="keyword">null</span>) &#123;</span><br><span class="line">			<span class="keyword">if</span> (head.getNext() != <span class="keyword">null</span>) &#123;</span><br><span class="line">				System.out.print(head.getData() + <span class="string">" , "</span>);</span><br><span class="line">			&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">				System.out.print(head.getData());</span><br><span class="line">			&#125;</span><br><span class="line">			head = head.getNext();</span><br><span class="line">		&#125;</span><br><span class="line">		System.out.println();</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// destroy the linked list</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">destroyStack</span><span class="params">(<span class="comment">/* ListNode&lt;E&gt; head */</span>)</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">		ListNode&lt;E&gt; auxilaryNode = <span class="keyword">null</span>, iterator = headNode;</span><br><span class="line">		<span class="keyword">while</span> (iterator != <span class="keyword">null</span>) &#123;</span><br><span class="line">			auxilaryNode = iterator.getNext();</span><br><span class="line">			iterator = <span class="keyword">null</span>;</span><br><span class="line">			iterator = auxilaryNode;</span><br><span class="line"></span><br><span class="line">			headNode = iterator;<span class="comment">// Set the node to be deleted as the header node.</span></span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span> (auxilaryNode == <span class="keyword">null</span>) &#123;</span><br><span class="line">			<span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// Test</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">		<span class="comment">// ListStack&lt;Integer&gt; stack = new ListStack&lt;Integer&gt;();</span></span><br><span class="line">		ListStack&lt;String&gt; stack = <span class="keyword">new</span> ListStack&lt;String&gt;();</span><br><span class="line">		stack.push(<span class="string">"A"</span>);</span><br><span class="line">		stack.push(<span class="string">"B"</span>);</span><br><span class="line">		stack.push(<span class="string">"C"</span>);</span><br><span class="line">		stack.push(<span class="string">"D"</span>);</span><br><span class="line">		stack.push(<span class="string">"E"</span>);</span><br><span class="line">		stack.push(<span class="string">"F"</span>);</span><br><span class="line">		stack.push(<span class="string">"G"</span>);</span><br><span class="line"></span><br><span class="line">		stack.getNodeByLoop(stack.headNode);</span><br><span class="line">		System.out.println(<span class="string">"The node to be poped : "</span> + stack.pop());</span><br><span class="line">		System.out.println(<span class="string">"The top node : "</span> + stack.top());</span><br><span class="line">		System.out.println(<span class="string">"Push a new node : "</span> + stack.push(<span class="string">"H"</span>));</span><br><span class="line">		System.out.println(<span class="string">"The top node : "</span> + stack.top());</span><br><span class="line">		System.out.println(<span class="string">"Determines whether the stack is empty : "</span> + stack.isEmpty());</span><br><span class="line">		System.out.println(<span class="string">"Pop all of nodes(success ?) : "</span> + stack.popAll());</span><br><span class="line">		System.out.println(<span class="string">"Determines whether the stack is empty : "</span> + stack.isEmpty());</span><br><span class="line">		System.out.println(<span class="string">"Push a new node : "</span> + stack.push(<span class="string">"I"</span>));</span><br><span class="line">		System.out.println(<span class="string">"Push a new node : "</span> + stack.push(<span class="string">"J"</span>));</span><br><span class="line">		System.out.println(<span class="string">"Push a new node : "</span> + stack.push(<span class="string">"K"</span>));</span><br><span class="line">		System.out.println(<span class="string">"Destroy the stack(success ?) : "</span> + stack.destroyStack());</span><br><span class="line">		System.out.println(<span class="string">"Determines whether the stack is empty : "</span> + stack.isEmpty());</span><br><span class="line"></span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/*## The program running results are as follows :</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">All of nodes of the linked list:  G , F , E , D , C , B , A</span></span><br><span class="line"><span class="comment">The node to be poped : G</span></span><br><span class="line"><span class="comment">The top node : F</span></span><br><span class="line"><span class="comment">Push a new node : [H]</span></span><br><span class="line"><span class="comment">The top node : H</span></span><br><span class="line"><span class="comment">Determines whether the stack is empty : false</span></span><br><span class="line"><span class="comment">Pop all of nodes : H</span></span><br><span class="line"><span class="comment">Pop all of nodes : F</span></span><br><span class="line"><span class="comment">Pop all of nodes : E</span></span><br><span class="line"><span class="comment">Pop all of nodes : D</span></span><br><span class="line"><span class="comment">Pop all of nodes : C</span></span><br><span class="line"><span class="comment">Pop all of nodes : B</span></span><br><span class="line"><span class="comment">Pop all of nodes : A</span></span><br><span class="line"><span class="comment">Pop all of nodes(success ?) : true</span></span><br><span class="line"><span class="comment">Determines whether the stack is empty : true</span></span><br><span class="line"><span class="comment">Push a new node : [I]</span></span><br><span class="line"><span class="comment">Push a new node : [J]</span></span><br><span class="line"><span class="comment">Push a new node : [K]</span></span><br><span class="line"><span class="comment">Destroy the stack(success ?) : true</span></span><br><span class="line"><span class="comment">Determines whether the stack is empty : true</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment"> */</span></span><br></pre></td></tr></table></figure>
<h3 id="栈的各种实现方法的比较"><a href="#栈的各种实现方法的比较" class="headerlink" title="栈的各种实现方法的比较"></a>栈的各种实现方法的比较</h3><ol>
<li><strong>递增策略和倍增策略的比较</strong></li>
</ol>
<ul>
<li><em>通过分析完成<code>n</code>个<code>push</code>操作的总时间开销<code>T(n)</code>来比较递增策略和倍增策略的区别.从长度为<code>1</code>的数组表示的空栈开始,一次<code>push</code>操作的平摊时间等于一组<code>push</code>操作的总时间开销的平均值.记为 : <code>T(n)/n</code></em></li>
<li><em><code>递增策略</code> : 实现<code>push</code>操作的平摊时间开销为<code>O(n)[O(n²)/n]</code> .</em></li>
<li><em><code>倍增策略</code> : 实现<code>push</code>操作的平摊时间开销为<code>O(n)[O(n)/n]</code> .</em></li>
</ul>
<ol start="2">
<li><strong>基于数组实现和基于链表实现的比较</strong><h4 id="a-：基于数组实现的栈"><a href="#a-：基于数组实现的栈" class="headerlink" title="(a) ：基于数组实现的栈"></a>(a) ：基于数组实现的栈</h4></li>
</ol>
<ul>
<li><em>各个操作都是常数时间开销.</em></li>
<li><em>每隔一段时间倍增操作的开销过大.</em></li>
<li><em>(从空栈开始)<code>n</code>个操作的任意序列的平摊时间开销为<code>O(n)</code>.</em><h4 id="b-：基于链表实现的栈"><a href="#b-：基于链表实现的栈" class="headerlink" title="(b) ：基于链表实现的栈"></a>(b) ：基于链表实现的栈</h4></li>
<li><em>栈规模的增加和减少都是很简洁.</em></li>
<li><em>各个操作都是常数时间开销.</em></li>
<li><em>每个操作都要使用额外的空间和时间开销来处理指针.</em></li>
</ul>
<h3 id="栈的应用-1"><a href="#栈的应用-1" class="headerlink" title="栈的应用"></a>栈的应用</h3><ol>
<li><em>举例<code>1</code> ：将用户输入的字符反转</em></li>
</ol>
<ul>
<li><p><em>首先定义一个基于简单数组的栈</em></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@ClassName</span>: SimpleStack</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span>: 栈</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span>: HuangYuhui</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@date</span>: Apr 10, 2019 8:50:56 PM</span></span><br><span class="line"><span class="comment"> * </span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">SimpleStack</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 栈的大小</span></span><br><span class="line">	<span class="keyword">private</span> <span class="keyword">int</span> maxSize;</span><br><span class="line">	<span class="comment">// 存储栈元素</span></span><br><span class="line">	<span class="keyword">private</span> <span class="keyword">char</span>[] stackArray;</span><br><span class="line">	<span class="comment">// 栈顶指针</span></span><br><span class="line">	<span class="keyword">private</span> <span class="keyword">int</span> topPointer;</span><br><span class="line"></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="title">SimpleStack</span><span class="params">(<span class="keyword">int</span> max)</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">		maxSize = max;</span><br><span class="line">		topPointer = -<span class="number">1</span>;</span><br><span class="line">		stackArray = <span class="keyword">new</span> <span class="keyword">char</span>[maxSize];</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 逐个向栈中压入元素</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">char</span> c)</span> </span>&#123;</span><br><span class="line">		stackArray[++topPointer] = c;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 逐个弹出栈中元素</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">char</span> <span class="title">pop</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">return</span> stackArray[topPointer--];</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 弹出栈中所有的元素</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">popAll</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">while</span> (!isEmpty()) &#123;</span><br><span class="line">			System.out.println(<span class="string">"pop element : "</span> + pop());</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 查看栈顶元素</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">char</span> <span class="title">peek</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">return</span> stackArray[topPointer];</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 判断栈是否为空</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="keyword">return</span> topPointer == -<span class="number">1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
<li><p><em>利用栈来反转字符</em></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@ClassName</span>: MyStack</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span>: 利用栈来反转字符串</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span>: HuangYuhui</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@date</span>: Apr 10, 2019 3:46:40 PM</span></span><br><span class="line"><span class="comment"> * </span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">ReversalString</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">private</span> String input;</span><br><span class="line">	<span class="keyword">private</span> String output;</span><br><span class="line"></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="title">ReversalString</span><span class="params">(String in)</span> </span>&#123;</span><br><span class="line">		<span class="keyword">this</span>.input = in;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 反转字符</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> String <span class="title">doReversal</span><span class="params">()</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">		<span class="keyword">int</span> stackSize = input.length();</span><br><span class="line">		SimpleStack stack = <span class="keyword">new</span> SimpleStack(stackSize);</span><br><span class="line"></span><br><span class="line">		<span class="comment">// 将字符逐个压入栈中</span></span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; input.length(); i++) &#123;</span><br><span class="line">			<span class="keyword">char</span> in = input.charAt(i);</span><br><span class="line">			stack.push(in);</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		<span class="comment">// 将字符逐个从栈中取出</span></span><br><span class="line">		output = <span class="string">""</span>;</span><br><span class="line">		<span class="keyword">while</span> (!stack.isEmpty()) &#123;</span><br><span class="line">			<span class="keyword">char</span> out = stack.pop();</span><br><span class="line">			output += out;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		<span class="keyword">return</span> output;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
<li><p><em>接收用户输入的字符并测试</em></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@ClassName</span>: ReversalStringTest</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span>: 测试反转字符程序</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span>: HuangYuhui</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@date</span>: Apr 10, 2019 8:53:24 PM</span></span><br><span class="line"><span class="comment"> * </span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">ReversalStringTest</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">static</span> BufferedReader bufferedReader;</span><br><span class="line"></span><br><span class="line">	<span class="meta">@Test</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">reversalTest</span><span class="params">()</span> <span class="keyword">throws</span> IOException </span>&#123;</span><br><span class="line">		String input, output;</span><br><span class="line"></span><br><span class="line">		<span class="keyword">while</span> (<span class="keyword">true</span>) &#123;</span><br><span class="line">			System.out.println(<span class="string">"Please enter a string : "</span>);</span><br><span class="line">			<span class="comment">// System.out.flush();</span></span><br><span class="line">			input = getString();</span><br><span class="line">			<span class="keyword">if</span> (input.equals(<span class="string">"exit"</span>)) &#123;</span><br><span class="line">				bufferedReader.close();</span><br><span class="line">				<span class="keyword">break</span>;</span><br><span class="line">			&#125;</span><br><span class="line"></span><br><span class="line">			<span class="comment">// 将字符串反转</span></span><br><span class="line">			ReversalString reversal = <span class="keyword">new</span> ReversalString(input);</span><br><span class="line">			output = reversal.doReversal();</span><br><span class="line"></span><br><span class="line">			System.out.println(<span class="string">"Reversed : "</span> + output);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="meta">@Test</span></span><br><span class="line">	<span class="meta">@Ignore</span></span><br><span class="line">	<span class="comment">// 测试BufferedString中的控制字符反转的方法</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">BufferedStringTest</span><span class="params">()</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">		StringBuffer stringBuffer = <span class="keyword">new</span> StringBuffer(<span class="string">"reverse"</span>);</span><br><span class="line"></span><br><span class="line">		System.err.println(<span class="string">"Reversed : "</span> + stringBuffer.reverse());</span><br><span class="line"></span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 通过缓冲流中的'readLine'方法高效读入用户输入的数据</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">static</span> String <span class="title">getString</span><span class="params">()</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">		String s = <span class="keyword">null</span>;</span><br><span class="line">		bufferedReader = <span class="keyword">new</span> BufferedReader(<span class="keyword">new</span> InputStreamReader(System.in));</span><br><span class="line">		<span class="keyword">try</span> &#123;</span><br><span class="line">			s = bufferedReader.readLine();</span><br><span class="line">		&#125; <span class="keyword">catch</span> (IOException e) &#123;</span><br><span class="line">			e.printStackTrace();</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> s;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
<li><p><em>程序运行结果如下 :</em></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">Please enter a string : </span><br><span class="line">my qq: <span class="number">3083968068</span></span><br><span class="line"></span><br><span class="line">Reversed : <span class="number">8608693803</span> :qq ym</span><br><span class="line"></span><br><span class="line">Please enter a string : </span><br><span class="line">exit</span><br></pre></td></tr></table></figure>
</li>
</ul>
<ol start="2">
<li><em>举例 ：检查用户输入的运算符(括号匹配)</em></li>
</ol>
<ul>
<li><em>首先定义一个基于简单数组的栈(同上,略写)</em></li>
<li><p><em>利用栈中入栈和出栈操作匹配括号符</em></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@ClassName</span>: BracketChecker</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span>: 匹配括号</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span>: HuangYuhui</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@date</span>: Apr 10, 2019 9:58:36 PM</span></span><br><span class="line"><span class="comment"> * </span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">BracketChecker</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">private</span> String input;</span><br><span class="line"></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="title">BracketChecker</span><span class="params">(String in)</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">		<span class="keyword">this</span>.input = in;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">chekc</span><span class="params">()</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">		<span class="keyword">boolean</span> flag_a = <span class="keyword">false</span>;</span><br><span class="line">		<span class="keyword">boolean</span> flag_b = <span class="keyword">false</span>;</span><br><span class="line">		<span class="keyword">int</span> stackSize = input.length();</span><br><span class="line">		SimpleStack stack = <span class="keyword">new</span> SimpleStack(stackSize);</span><br><span class="line"></span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; input.length(); i++) &#123;</span><br><span class="line">			<span class="keyword">char</span> in = input.charAt(i);</span><br><span class="line"></span><br><span class="line">			<span class="keyword">switch</span> (in) &#123;</span><br><span class="line">			<span class="keyword">case</span> <span class="string">'&#123;'</span>:</span><br><span class="line">			<span class="keyword">case</span> <span class="string">'('</span>:</span><br><span class="line">			<span class="keyword">case</span> <span class="string">'['</span>:</span><br><span class="line">			<span class="keyword">case</span> <span class="string">'&lt;'</span>:</span><br><span class="line">				stack.push(in);</span><br><span class="line">				<span class="keyword">break</span>;</span><br><span class="line">			<span class="keyword">case</span> <span class="string">'&#125;'</span>:</span><br><span class="line">			<span class="keyword">case</span> <span class="string">')'</span>:</span><br><span class="line">			<span class="keyword">case</span> <span class="string">']'</span>:</span><br><span class="line">			<span class="keyword">case</span> <span class="string">'&gt;'</span>:</span><br><span class="line">				<span class="comment">// 括号匹配</span></span><br><span class="line">				<span class="keyword">if</span> (!stack.isEmpty()) &#123;</span><br><span class="line">					<span class="keyword">char</span> out = stack.pop();</span><br><span class="line">					<span class="keyword">if</span> ((in == <span class="string">'&#125;'</span> &amp;&amp; out != <span class="string">'&#123;'</span>) || (in == <span class="string">')'</span> &amp;&amp; out != <span class="string">'('</span>) || (in == <span class="string">']'</span> &amp;&amp; out != <span class="string">'['</span>)</span><br><span class="line">							|| (in == <span class="string">'&gt;'</span> &amp;&amp; out != <span class="string">'&lt;'</span>)) &#123;</span><br><span class="line">						System.err.println(<span class="string">"error : "</span> + in + <span class="string">" at "</span> + i);</span><br><span class="line">					&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">						flag_a = <span class="keyword">true</span>;</span><br><span class="line">					&#125;</span><br><span class="line">				&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">					System.err.println(<span class="string">"error : "</span> + in + <span class="string">" at "</span> + i);</span><br><span class="line">					flag_a = <span class="keyword">false</span>;</span><br><span class="line">				&#125;</span><br><span class="line"></span><br><span class="line">				<span class="keyword">break</span>;</span><br><span class="line">			<span class="comment">// 只检查括号</span></span><br><span class="line">			<span class="keyword">default</span>:</span><br><span class="line">				<span class="keyword">break</span>;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		<span class="comment">// 如果匹配成功,循环结束后栈中理应为空.</span></span><br><span class="line">		<span class="keyword">if</span> (!stack.isEmpty()) &#123;</span><br><span class="line">			System.out.println(<span class="string">"Error : missing right delimiter."</span>);</span><br><span class="line">		&#125; <span class="keyword">else</span> &#123;</span><br><span class="line">			flag_b = <span class="keyword">true</span>;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		<span class="keyword">if</span> (flag_a &amp;&amp; flag_b) &#123;</span><br><span class="line">			System.out.println(<span class="string">"Success !"</span>);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
<li><p><em>接收用户输入的运算符并测试匹配程序</em></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@ClassName</span>: BracketCheckerTest</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span>: 测试匹配括号符程序</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span>: HuangYuhui</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@date</span>: Apr 10, 2019 9:58:55 PM</span></span><br><span class="line"><span class="comment"> * </span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">BracketCheckerTest</span> </span>&#123;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">static</span> BufferedReader bufferedReader;</span><br><span class="line">	</span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> <span class="keyword">throws</span> IOException </span>&#123;</span><br><span class="line">		</span><br><span class="line">		String input;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">while</span>(<span class="keyword">true</span>) &#123;</span><br><span class="line">			System.out.println(<span class="string">"Please enter containing delimiters : "</span>);</span><br><span class="line">			System.out.flush();</span><br><span class="line">			input = getString();</span><br><span class="line">			<span class="keyword">if</span>(input.equals(<span class="string">"exit"</span>)) &#123;</span><br><span class="line">				bufferedReader.close();</span><br><span class="line">				<span class="keyword">break</span>;</span><br><span class="line">			&#125;</span><br><span class="line">			</span><br><span class="line">			BracketChecker checker = <span class="keyword">new</span> BracketChecker(input);</span><br><span class="line">			checker.chekc();</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 通过缓冲流中的'readLine'方法高效读入用户的数据.</span></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">static</span> String <span class="title">getString</span><span class="params">()</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">		String s = <span class="keyword">null</span>;</span><br><span class="line">		bufferedReader = <span class="keyword">new</span> BufferedReader(<span class="keyword">new</span> InputStreamReader(System.in));</span><br><span class="line">		<span class="keyword">try</span> &#123;</span><br><span class="line">			s = bufferedReader.readLine();</span><br><span class="line">		&#125; <span class="keyword">catch</span> (IOException e) &#123;</span><br><span class="line">			e.printStackTrace();</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> s;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
<li><p><em>程序运行结果如下 :</em></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line">Please enter containing delimiters : </span><br><span class="line">&#123;[&lt;a&gt;b]c)d&#125;efg</span><br><span class="line">error : ) at <span class="number">8</span></span><br><span class="line">error : &#125; at <span class="number">10</span></span><br><span class="line"></span><br><span class="line">Please enter containing delimiters : </span><br><span class="line">&#123;([&lt;a&gt;b]c)defg</span><br><span class="line">Error : missing right delimiter.</span><br><span class="line"></span><br><span class="line">Please enter containing delimiters : </span><br><span class="line">&#123;([&lt;a&gt;b]cd&#125;efg</span><br><span class="line">error : &#125; at <span class="number">10</span></span><br><span class="line">Error : missing right delimiter.</span><br><span class="line"></span><br><span class="line">Please enter containing delimiters : </span><br><span class="line">&#123;([&lt;a&gt;b]c)d&#125;efg</span><br><span class="line">Success !</span><br><span class="line"></span><br><span class="line">Please enter containing delimiters : </span><br><span class="line">exit</span><br></pre></td></tr></table></figure></li>
</ul>

        </div>

        <blockquote class="post-copyright">
    
    <div class="content">
        
<span class="post-time">
    Last updated: <time datetime="2019-10-31T05:19:50.761Z" itemprop="dateUpdated">2019-10-31 05:19:50</time>
</span><br>


        
    </div>
    
    <footer>
        <a href="http://yoursite.com">
            <img src="/img/my-portrait.jpg" alt="黄宇辉">
            黄宇辉
        </a>
    </footer>
</blockquote>

        
<div class="page-reward">
    <a id="rewardBtn" href="javascript:;" class="page-reward-btn waves-effect waves-circle waves-light">赏</a>
</div>



        <div class="post-footer">
            
	<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/Data-Structures-and-Algorithms/">Data Structures and Algorithms</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/Java/">Java</a></li></ul>


            
<div class="page-share-wrap">
    

<div class="page-share" id="pageShare">
    <ul class="reset share-icons">
      <li>
        <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=http://yoursite.com/2019/04/13/详解Stack的实现方式及其应用/&title=《详解Stack的实现方式及其应用》 — 欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~&pic=http://yoursite.com/img/my-portrait.jpg" data-title="微博">
          <i class="icon icon-weibo"></i>
        </a>
      </li>
      <li>
        <a class="weixin share-sns wxFab" href="javascript:;" data-title="微信">
          <i class="icon icon-weixin"></i>
        </a>
      </li>
      <li>
        <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=http://yoursite.com/2019/04/13/详解Stack的实现方式及其应用/&title=《详解Stack的实现方式及其应用》 — 欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~&source=My Personal Website For Blog" data-title=" QQ">
          <i class="icon icon-qq"></i>
        </a>
      </li>
      <li>
        <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=http://yoursite.com/2019/04/13/详解Stack的实现方式及其应用/" data-title=" Facebook">
          <i class="icon icon-facebook"></i>
        </a>
      </li>
      <li>
        <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《详解Stack的实现方式及其应用》 — 欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~&url=http://yoursite.com/2019/04/13/详解Stack的实现方式及其应用/&via=http://yoursite.com" data-title=" Twitter">
          <i class="icon icon-twitter"></i>
        </a>
      </li>
      <li>
        <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=http://yoursite.com/2019/04/13/详解Stack的实现方式及其应用/" data-title=" Google+">
          <i class="icon icon-google-plus"></i>
        </a>
      </li>
    </ul>
 </div>



    <a href="javascript:;" id="shareFab" class="page-share-fab waves-effect waves-circle">
        <i class="icon icon-share-alt icon-lg"></i>
    </a>
</div>



        </div>
    </div>

    
<nav class="post-nav flex-row flex-justify-between">
  
    <div class="waves-block waves-effect prev">
      <a href="/2019/04/14/Java-annotation/" id="post-prev" class="post-nav-link">
        <div class="tips"><i class="icon icon-angle-left icon-lg icon-pr"></i> Prev</div>
        <h4 class="title">Java annotation</h4>
      </a>
    </div>
  

  
    <div class="waves-block waves-effect next">
      <a href="/2019/04/12/A-simple-MVC-example/" id="post-next" class="post-nav-link">
        <div class="tips">Next <i class="icon icon-angle-right icon-lg icon-pl"></i></div>
        <h4 class="title">A simple MVC example</h4>
      </a>
    </div>
  
</nav>



    




















</article>

<div id="reward" class="page-modal reward-lay">
    <a class="close" href="javascript:;"><i class="icon icon-close"></i></a>
    <h3 class="reward-title">
        <i class="icon icon-quote-left"></i>
        thanks ~
        <i class="icon icon-quote-right"></i>
    </h3>
    <div class="reward-content">
        
        <div class="reward-code">
            <img id="rewardCode" src="/img/Wechat_appreciates.png" alt="打赏二维码">
        </div>
        
    </div>
</div>



</div>

        <footer class="footer">
    <div class="top">
        

        <p>
            
                <span><a href="/atom.xml" target="_blank" class="rss" title="rss"><i class="icon icon-lg icon-rss"></i></a></span>
            
            <span>This blog is licensed under a <a rel="license" href="https://creativecommons.org/licenses/by/4.0/">Creative Commons Attribution 4.0 International License</a>.</span>
        </p>
    </div>
    <div class="bottom">
        <!-- 统计网站用户访问量. 技术支持：不蒜子(http://busuanzi.ibruce.info/) ————> Mar 13,2019 -->
        <p>
            <font style='font-size: 12px;color:springgreen'>
                    <div align="center">
                        <!-- 安装脚本 -->
                        <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
                        <!-- 安装标签 -->
                        <span id="busuanzi_container_site_pv">
                            ◎用户总访问量 : <span id="busuanzi_value_site_pv"></span> 次 ~ &nbsp&nbsp
                        </span>
                        <span id="busuanzi_container_site_uv">
                            ◎总访客数(（づ￣3￣）づ╭❤～) : <span id="busuanzi_value_site_uv"></span>人 ~
                        </span>
                    </div>
                </font>
            </p>
            <!---------->
            <p>
                <font style='font-size: 10px'>
                    <span>黄宇辉 &copy; 2019</span>
                    <span>
                        
                        Blog source <a href="https://github.com/YUbuntu0109/YUbuntu0109.github.io" target="_blank">Github</a> 
                        Power by <a href="http://hexo.io/" target="_blank">Hexo</a>
                        Theme <a href="https://github.com/yscoder/hexo-theme-indigo" target="_blank">indigo</a>
                    </span>
                </font>
            </p>
        </div>
    </footer>
    </main>
    <div class="mask" id="mask"></div>
<a href="javascript:;" id="gotop" class="waves-effect waves-circle waves-light"><span class="icon icon-lg icon-chevron-up"></span></a>



<div class="global-share" id="globalShare">
    <ul class="reset share-icons">
      <li>
        <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=http://yoursite.com/2019/04/13/详解Stack的实现方式及其应用/&title=《详解Stack的实现方式及其应用》 — 欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~&pic=http://yoursite.com/img/my-portrait.jpg" data-title="微博">
          <i class="icon icon-weibo"></i>
        </a>
      </li>
      <li>
        <a class="weixin share-sns wxFab" href="javascript:;" data-title="微信">
          <i class="icon icon-weixin"></i>
        </a>
      </li>
      <li>
        <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=http://yoursite.com/2019/04/13/详解Stack的实现方式及其应用/&title=《详解Stack的实现方式及其应用》 — 欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~&source=My Personal Website For Blog" data-title=" QQ">
          <i class="icon icon-qq"></i>
        </a>
      </li>
      <li>
        <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=http://yoursite.com/2019/04/13/详解Stack的实现方式及其应用/" data-title=" Facebook">
          <i class="icon icon-facebook"></i>
        </a>
      </li>
      <li>
        <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《详解Stack的实现方式及其应用》 — 欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~&url=http://yoursite.com/2019/04/13/详解Stack的实现方式及其应用/&via=http://yoursite.com" data-title=" Twitter">
          <i class="icon icon-twitter"></i>
        </a>
      </li>
      <li>
        <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=http://yoursite.com/2019/04/13/详解Stack的实现方式及其应用/" data-title=" Google+">
          <i class="icon icon-google-plus"></i>
        </a>
      </li>
    </ul>
 </div>


<div class="page-modal wx-share" id="wxShare">
    <a class="close" href="javascript:;"><i class="icon icon-close"></i></a>
    <p>扫一扫，分享到微信</p>
    <img src="//api.qrserver.com/v1/create-qr-code/?data=http://yoursite.com/2019/04/13/详解Stack的实现方式及其应用/" alt="微信分享二维码">
</div>




    <script src="//cdn.bootcss.com/node-waves/0.7.4/waves.min.js"></script>
<script>
var BLOG = { ROOT: '/', SHARE: true, REWARD: true };


</script>

<script src="//unpkg.com/hexo-theme-material-indigo@latest/js/main.min.js"></script>


<div class="search-panel" id="search-panel">
    <ul class="search-result" id="search-result"></ul>
</div>
<template id="search-tpl">
<li class="item">
    <a href="{path}" class="waves-block waves-effect">
        <div class="title ellipsis" title="{title}">{title}</div>
        <div class="flex-row flex-middle">
            <div class="tags ellipsis">
                {tags}
            </div>
            <time class="flex-col time">{date}</time>
        </div>
    </a>
</li>
</template>

<script src="//unpkg.com/hexo-theme-material-indigo@latest/js/search.min.js" async></script>








<script>
(function() {
    var OriginTitile = document.title, titleTime;
    document.addEventListener('visibilitychange', function() {
        if (document.hidden) {
            document.title = 'Where are you going ?';
            clearTimeout(titleTime);
        } else {
            document.title = 'As long as you love me ~';
            titleTime = setTimeout(function() {
                document.title = OriginTitile;
            },2000);
        }
    });
})();
</script>



</body>
</html>
